This invention concerns the field of reduced hardware techniques for generation of Fourier transformations.
A transform is an alternative technique that can be applied to solve a mathematical problem. Conventional techniques apply mathematics directly to the problem, whereas a transform will convert (or transform) the problem into another form that is sometimes simpler to calculate. The results of the transform calculation will then require another conversion to return the problem back to the original format. Many times the conversion can use constants or a lookup table, which can greatly simplify the problem. This is the case with the Fourier transform.
The Fourier transform is a principle analytical tool in many diverse fields, including linear systems, optics, probability theory, quantum physics, antennas, radar, signal analysis and global positioning systems. This transform can be expressed in terms of a discrete solution, called the discrete Fourier transform. The complexity of computing the discrete Fourier transform is often stated in terms of N.sup.2, the square of the number of sample points examined. The discrete Fourier transform has found relatively few applications due to its complexity, even given the tremendous computational power and memory of modern processors.
The basic Fourier transform operation when applied to a waveform can decompose a complex waveform into a set of simple sinusoidal waveforms whose sum recreates the initial waveform. The simple waveforms have a representation as an amplitude and frequency. Mathematically, this can be represented as: ##EQU1## where ##EQU2## is the kernel function, a constant value in the Fourier transform, with j=-1 and N is the total number of input points and where X(k) is the kth component in the frequency domain, and x(n) is the input data. On the right side of Eq. 1, k and n are variables. In Eq. 1, therefore, the Fourier transformation is obtained from multiplication of the input data and the kernel function. The present invention simplifies the apparatus used to generate a Fourier transform and thereby reduces size and complexity of the associated hardware. The Fourier transform concepts used in the present invention are novel in that the mathematical operation mechanizations needed to accomplish the Fourier transform are addition and subtraction and necessary hardware components are limited to adders; the requirement for multiplication operations in performing the Fourier transform is eliminated.